package permute

func permute(nums []int) [][]int {
	m := make(map[int]struct{}, len(nums))
	var s []int
	var ans [][]int
	var backtrack func(nums []int, s []int)
	backtrack = func(nums []int, s []int) {
		if len(s) == len(nums) {
			// append ans
			news := make([]int, len(s))
			copy(news, s)
			ans = append(ans, news)
			return
		}
		for i := 0; i < len(nums); i++ {
			if _, ok := m[nums[i]]; ok {
				continue
			}
			m[nums[i]] = struct{}{}
			s = append(s, nums[i])
			backtrack(nums, s)
			delete(m, nums[i])
			s = s[:len(s)-1]
		}
	}
	backtrack(nums, s)
	return ans
}
